package madixin.t279;

import java.util.LinkedList;
import java.util.List;

class Solution {
    public int numSquares(int n) {
        List<Integer> squareList = genSquareList(n);
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int square : squareList) {
                if (square > i) {
                    break;
                }
                min = Math.min(min, dp[i - square] + 1);
            }
            dp[i] = min;
        }
        return dp[n];
    }

    private List<Integer> genSquareList(int n) {
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            if (square > n) {
                break;
            }
            list.add(square);
        }
        return list;
    }
}